package offer.diff;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * @author DengYuan2
 * @create 2021-03-21 19:42
 */
public class n_39 {
    public static void main(String[] args) {
        n_39 n = new n_39();
        int[] arr = {1,2,3,2,2,2,5,4,2};
        int res = n.MoreThanHalfNum_Solution(arr);
        System.out.println(res);
    }

    /**
     使用 cnt 来统计一个元素出现的次数，当遍历到的元素和统计元素相等时，
     令 cnt++，否则令 cnt--。如果前面查找了 i 个元素，且 cnt == 0，
     说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2 ，
     因为如果多于 i / 2 的话 cnt 就一定不会为 0 。
     此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。

     */
    public int MoreThanHalfNum_Solution(int [] array) {
        int count=1;
        int val = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i]==val){
                count++;
            }else {
                count--;
            }
            if(count==0){
                val=array[i];
                count=1;
            }

        }
        count=0;
        for (int i = 0; i < array.length; i++) {
            if (array[i]==val){
                count++;
            }
        }
        return count>array.length/2?val:0;
    }

    /**
     * 用hasmap就算了吧
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution2(int [] array) {
        int len = array.length/2;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(len );
        for (int i = 0; i < array.length; i++) {
            map.put(array[i],map.getOrDefault(array[i],0)+1);
        }
        Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<Integer, Integer> next = iterator.next();
            if(next.getValue()>len){
                return next.getKey();
            }
        }
        return 0;
    }

}
